\section{Semantics of predication logic}

\begin{enumerate}[(a)]

	%A
	\item 
		\begin{enumerate}[(1)]
			$\forall x \neg ( Q(x) \wedge \neg T(x))$		\\
			$\neg N(a)$																	\\
			$Q(a)$																			\\
			$T(a)$																			\\
			$N(b)$																			\\
			$\neg Q(b)$																	\\
			$\neg T(b)$																	\\
		\end{enumerate}
		
		$N^K = R_0$, $Q^K = R_1$, $T^K = R_2$, $a^K = b_0$, $b^K = b_1$
				
		$K$= $<$$D;R_0,R_1,R_2;b_0,b_1$$>$		\\
		
		\begin{align*}
			D   &= \left\{ b_0, b_1, b_2, b_3 \right\}		\\
			R_0 &= \left\{ b_1, b_2 \right\}							\\
			R_1 &= \left\{ b_0, b_2 \right\}							\\
			R_2 &= \left\{ b_0, b_2, b_3 \right\}					\\
		\end{align*}
	
	%B
	\item
		\begin{enumerate}[(i)]
		%i
		\item $ \forall x ((A(x) \wedge \neg B(x) ) \rightarrow \exists y (R(x,y) \wedge R(y,y))) $ \\
			The formula can only be false if the antecedent equals true and the consequent equals false. The antecedent is only true for 
			$d_2$ and $d_3$ according to $\forall x (A(x) \wedge \neg B(x))$, this means that the consequent needs to be true for 
			$d_2$ and $d_3$ to make the formula true.\\
			
			$d_2$ Has a relation to $d_3$ and $d_3$ has a relation to its self, that means the formula is true for $x=d_2$ and $y=d_3$. \\
			
			$d_3$ Has a relation to $d_4$ and itself $d_3$. This means that the antecedent is true when $y$ equals $d_3$, and thus the formula is true for $d_3$. \\
			
			Hence the formula is true for the first-order language L.
		
		%ii
		\item $\exists x ((A(x) \wedge B(x)) \wedge \exists y(R(x,y) \wedge B(y)))$ \\
			
			The first part $(A(x) \wedge B(x))$ of the formula is only true for $d_0$, that means $d_0$ needs a relation with an element in $B$, but $d_0$ only has a 
			relation with $d_2$ and that element is not in $B$. This means that this formula is not true for the first-order language L.
		
		%iii
		\item $\neg \forall x(A(x) \vee \neg \exists y(A(y) \wedge R(y,x)))$ \\
			The formula can be rewritten as follows:
			\begin{align*}
				\neg \forall x(A(x) 			&\vee \neg \exists y(A(y) \wedge R(y,x))) \\
				\exists x \neg ((A(x) 	&\vee \neg \exists y(A(y) \wedge R(y,z))) \\
				\exists x (\neg A(x) 	&\wedge \text{\space\space}\exists y(A(y) \wedge R(y,x))) \\
			\end{align*}
			
			Hence there must be one element in $A$ that has a relation to one element not in $A$. This is the case for $x=d_4$ and $y=d_3$ so the formula is true for the first-order language L.
		\end{enumerate}
		
	\clearpage
	%C
	\item 
			\begin{align*}
				S &= \left\{ D;R_0,R_1,R_3 \right\}  \\
				D &= \left\{ d_0,d_1,d_2,d_3 \right\}  \\
				R_0 &= \left\{ d_1,d_2 \right\}  \\
				R_1 &= \left\{ d_1 \right\}  \\
				R_2 &= \left\{ (d_0,d_0),(d_0,d_1),(d_0,d_2),(d_3,d_3) \right\}  \\
			\end{align*}
			
			$A^s=R_0$, $B^s=R_1$, $R^s=R_2$
			
			\begin{figure}[!ht]
			\centerline{\includegraphics[width=8cm]{diagram.png}}
			\end{figure}
			% TODO LEGENDA MAKEN

		\begin{enumerate}[(i)]
		%i
			\item $\forall x((A(x)\wedge \neg B(x)) \rightarrow \exists y (R(x,y) \wedge \neg B(y))) $ \\
				The formula can only be false if the antecedent equals true and the consequent false. The only variable that make the antecedent $((A(x)\wedge \neg B(x))$ true equals $d_2$, according to
				the formula  there must be an $y$ that makes the consequent $\exists y (R(x,y) \wedge \neg B(y))$ true. This is the case for $d_0$ hence the formula is true for the first-order language S.
				 
		%ii	
			\item $\exists x((\neg A(x) \wedge \neg B(x)) \wedge \exists y(R(x,y) \wedge A(y))) $ \\
				To make the formula true we just need an element $x$ and $y$ to make it true, if we take $x=d_0$ and $y=d_1$ or$x=d_0$ and $y=d_2$ the formula will be true. 
				Hence the formula is true for the first-order language S.
				
		%iii	
			\item $\exists z ((\neg A(z) \wedge \neg B(z)) \wedge \neg \exists y (A(y) \wedge R(z,y)))$ \\
				The formula can be rewritten as follows: 
				$\exists z ((\neg A(z) \wedge \neg B(z)) \wedge \forall y \neg (A(y) \wedge R(z,y)))$ \\
				$\exists z ((\neg A(z) \wedge \neg B(z)) \wedge \forall y (\neg A(y) \vee \neg R(z,y)))$ \\
				
				To make the formula true we need at least one $z$ for which all the combinations of $y$ are true. The first part of the formula $(\neg A(z) \wedge \neg B(z))$ is only true for $d_0$ and $d_3$, 
				but only for $d_3$ the second part $\forall y (\neg A(y) \vee \neg R(z,y))$ is true in all cases of $y$. This make the formula true for the first-order language S, as there is one $z=d_3$ 
				that makes the formula true in all the cases of $y$.
		%iv	
			\item $\neg \forall x (A(x) \vee (B(x) \vee \neg R(x,x)))$ \\
				The formula can be rewritten as follows: 
				$ \exists x \neg (A(x) \vee (B(x) \vee \neg R(x,x)))$ \\
				$ \exists x (\neg A(x) \wedge \neg(B(x) \vee \neg R(x,x)))$ \\
				$ \exists x (\neg A(x) \wedge (\neg B(x) \wedge  R(x,x)))$
				
				This means that to make the formula true we need at least one element that is not in A and not in B and has a relation with itself, this is true for $d_0$ and $d_3$. 
				Hence the formula is true for the	first order language S as there are two elements $d_0$ and $d_3$ that make the formula true where we needed one or more.
		
		\end{enumerate}
\end{enumerate}